from collections import defaultdict
import time

def calcTime(func):
        '''
        函数修饰器, 用来计算各个排序算法的执行时间
        最终返回一个 list [temp, time_sum]
        '''
        def warpper (*args, **kwds):
            time_start = time.perf_counter()
            temp = func(*args, **kwds)
            time_end = time.perf_counter()
            time_sum = time_end - time_start
            return [temp, time_sum*1000]
        return warpper

class Solution:
    @calcTime
    def strangePrinter(self, s : str) -> int:
        n = len(s)
        f = [defaultdict(int) for i in range(n)]
        for i in range(n-1, -1, -1):
            f[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    f[i][j] = f[i][j-1]
                else:
                    minn = 1e9
                    for k in range(i, j):
                        minn = min(minn, f[i][k] + f[k+1][j])
                    f[i][j] = minn
        return f[0][n-1]


if __name__ == '__main__':
    s = "aaabbb"
    sol = Solution()
    re = sol.strangePrinter(s)
    print(re)